Quick Sorting

퀵 정렬(Quick Sorting): 분할 정복 기반(Divide and Conquer)
퀵 정렬은 최악의 경우 \Theta(n^2)에 정렬하지만,
평균 수행 시간이 \Theta(nlgn) 으로 매우 효율적인다.
( \Theta(nlgn)의 상수 값도 작은 값을 가짐 )

또한, 내부정렬 구조로 적은 메모리 시스템에서도 구동할 수 있다.

- QuickSort(arr, p, r)
- Partition(arr, p, r)
#include <iostream>
#define swap(i, j){int tmp=i; i=j; j=tmp;}
using namespace std;
int Partition(int*, int, int);
void QuickSort(int*arr, int p, int r){
if(p<r){
int q=Partition(arr, p, r);
QuickSort(arr, p, q-1);
QuickSort(arr, q+1, r);
}
}
int Partition(int* arr, int p, int r){
int x=arr[r];
int i=p-1;
for(int j=p; j<r; ++j){
if(arr[j]<=x){
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i+1], arr[r]);
return i+1; // crt index
}
int main(void){
int arr[]={5, 3, 6, 2, 7, 9};
int size=sizeof(arr)/sizeof(int);
QuickSort(arr, 0, size-1);
for(int i=0; i<size; ++i) cout<<arr[i]<<" ";
cout<<endl;
return 0;
}
Partition(Arr, p, r) 1. p≤k≤i 이면, A[k]≤x 다. 2. i+1≤k≤j−1 이면, A[k]>x 다. 3. k=r 이면 A[k]=x 다.
Randomized Quick Sorting
#include <iostream>
#include <random>
#define swap(i, j){int tmp=i; i=j; j=tmp;}
using namespace std;
std::random_device rd;
std::mt19937 gen(rd());
int Partition(int* arr, int p, int r){
int x=arr[r];
int i=p-1;
for(int j=p; j<r; ++j){
if(arr[j]<=x){
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i+1], arr[r]);
return i+1; // crt index
}
int Randomized_Partition(int* arr, int p, int r){
std::uniform_int_distribution<int> runif(p, r);
int i=runif(gen);
swap(arr[r], arr[i]);
return Partition(arr, p, r);
}
void Randomized_QuickSort(int* arr, int p, int r){
if(p<r){
int q=Randomized_Partition(arr, p, r);
Randomized_QuickSort(arr, p, q-1);
Randomized_QuickSort(arr, q+1, r);
}
}
int main(void){
int arr[]={5, 3, 6, 2, 7, 9};
int size=sizeof(arr)/sizeof(int);
Randomized_QuickSort(arr, 0, size-1);
for(int i=0; i<size; ++i) cout<<arr[i]<<" ";
cout<<endl;
return 0;
}